package 栈与队列;

/**
 * 124. 二叉树中的最大路径和
 *
 * 二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
 * 路径和 是路径中各节点值的总和。
 * 给你一个二叉树的根节点 root ，返回其 最大路径和 。
 *
 * 解题思路
 * 要解决二叉树中的最大路径和问题，我们需要找到所有可能路径中和最大的值。路径可以是任意节点之间的路径，
 * 但必须满足父子关系连接。核心思路是通过递归遍历每个节点，并计算以当前节点为“中间节点”的最大路径和。具体步骤如下：
 *
 * 递归定义：
 * 对于每个节点，计算其左子树和右子树能提供的最大贡献值。如果子树的贡献值为负数，则舍弃（贡献值取0）。
 * 以当前节点为中间节点的最大路径和为：节点值 + 左子树贡献 + 右子树贡献。
 * 维护一个全局变量 maxSum，记录遍历过程中遇到的最大路径和。
 * 递归返回值：
 * 递归函数返回当前节点能提供的单边最大贡献值（即只能选择左或右子树的一条路径），即 节点值 + max(左子树贡献, 右子树贡献)。
 * 终止条件：
 * 当前节点为 null 时，返回0（表示无贡献）。
 */
public class L_124 {

    private int maxSum = Integer.MIN_VALUE; // 全局变量记录最大路径和

    public int maxPathSum(TreeNode root) {
        caclulateMax(root);
        return maxSum;
    }

    private int caclulateMax(TreeNode root){
        if(root == null){
            return 0;
        }

        // 递归计算左右子树的最大贡献值 (若为负数则取0)
        int left = Math.max(caclulateMax(root.left),0);
        int right = Math.max(caclulateMax(root.right),0);

        // 计算当前节点为中间节点的最大路径和
        int sum = root.val + left + right;
        maxSum = Math.max(maxSum, sum); // 更新全局最大路径和
        // 返回当前节点为中间节点的最大路径和(只能选择左或右子树的一条路径)
        return root.val + Math.max(left, right);
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
